#include <iostream>
#include <vector>
#include <string>
#include <map>
using namespace std;

int ans;                                          // 逆序数
void Merge(string &a, int low, int mid, int high) // 两个相邻有序段归并
{
    int i = low;
    int j = mid + 1;
    int k = 0;
    string tmp;
    while (i <= mid && j <= high) // 二路归并
    {
        if (a[i] > a[j])
        {
            tmp.push_back(a[j++]);
            ans += mid - i + 1;
        }
        else
            tmp.push_back(a[i++]);
    }
    while (i <= mid)
        tmp.push_back(a[i++]);
    while (j <= high)
        tmp.push_back(a[j++]);

    for (int m = 0; m < tmp.size(); m++)
        a[low + m] = tmp[m];
}

void Merge_sort(string &a, int low, int high) //递归二路归并排序
{
    if (low < high)
    {
        int mid = (low + high) / 2;
        Merge_sort(a, low, mid);
        Merge_sort(a, mid + 1, high);
        Merge(a, low, mid, high);
    }
}

int Inversion(string a, int n) //二路归并法求字符串a的逆序数
{
    ans = 0;
    Merge_sort(a, 0, n - 1);
    return ans;
}

int main()
{
    vector<string> vec{"AACATGAAGG", "TTTTGGCCAA",
                       "TTTGGCCAAA", "GATCAGATTT",
                       "CCCGGGGGGA", "ATCGATGCAT"};

    map<int, string> inv_map;

    for (string dna : vec)
    {
        inv_map[Inversion(dna, dna.size())] = dna;
    }

    for (auto it : inv_map)
    {
        cout << it.second << endl;
    }

    return 0;
}